#ifndef GRAPH_H_
#define GRAPH_H_

#include <algorithm>
#include <cstdio>
#include <queue>
#include <string>
#include <vector>


namespace lxj
{
// 建图
class Graph {
    // 邻接矩阵
    std::vector<std::vector<int>> adj_matrix;

    // 邻接表
    std::vector<std::vector<std::pair<int, int>>> adj_list;

    // 链式前向星
    std::vector<int> head;
    std::vector<int> next;
    std::vector<int> to;
    std::vector<int> weight;
    int              cnt;

private:
    // 三种方式建立有向图带权图
    inline void directGraph(const std::vector<std::vector<int>>& edges)
    {
        // 邻接矩阵
        for (auto& edge : edges) {
            adj_matrix[edge[0]][edge[1]] = edge[2];
        }

        // 邻接表
        for (auto& edge : edges) {
            adj_list[edge[0]].push_back({edge[1], edge[2]});
        }

        // 链式表
        for (auto& edge : edges) {
            addEdge(edge[0], edge[1], edge[2]);
        }
    }

    // 三种方式建立无向图带权图
    inline void undirectGraph(const std::vector<std::vector<int>>& edges)
    {
        for (auto& edge : edges) {
            adj_matrix[edge[0]][edge[1]] = edge[2];
            adj_matrix[edge[1]][edge[0]] = edge[2];
        }

        for (auto& edge : edges) {
            adj_list[edge[0]].push_back({edge[1], edge[2]});
            adj_list[edge[1]].push_back({edge[0], edge[2]});
        }

        for (auto& edge : edges) {
            addEdge(edge[0], edge[1], edge[2]);
            addEdge(edge[1], edge[0], edge[2]);
        }
    }

    inline void addEdge(int u, int v, int w)
    {
        // u -> v , 边权重是w
        next[cnt]   = head[u];
        to[cnt]     = v;
        weight[cnt] = w;
        head[u]     = cnt++;
    }

public:
    Graph(int n, std::vector<std::vector<int>>& edges, bool dg = true)
    {
        // 初始化邻接矩阵
        adj_matrix = std::vector<std::vector<int>>(n + 1, std::vector<int>(n + 1));
        // 初始化领接表
        adj_list = std::vector<std::vector<std::pair<int, int>>>(n + 1);
        // 初始化链式表
        head   = std::vector<int>(n + 1);
        next   = std::vector<int>(2 * (n + 1));
        to     = std::vector<int>(2 * (n + 1));
        weight = std::vector<int>(2 * (n + 1));
        cnt    = 1;

        dg ? directGraph(edges) : undirectGraph(edges);
    }

    inline void traversal()
    {
        int n = head.size() > 1 ? head.size() - 1 : 1;
        std::printf("邻接矩阵：\n");
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                std::printf("%d, ", adj_matrix[i][j]);
            }
            std::puts("");
        }

        std::printf("邻接表遍历：\n");
        for (int i = 1; i <= n; i++) {
            std::printf("%d (邻居，边权)：", i);
            for (auto& edge : adj_list[i]) std::printf("(%d,%d)", edge.first, edge.second);
            std::puts("");
        }

        std::printf("链式前向星：\n");
        for (int i = 1; i <= n; i++) {
            std::printf("%d (邻居，边权)：", i);
            for (int ei = head[i]; ei > 0; ei = next[ei])
                std::printf("(%d,%d)", to[ei], weight[ei]);
            std::puts("");
        }
    }
};

// 拓扑排序模版（Leetcode）
// 邻接表建图（动态方式）
// 课程表II
// 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1
// 给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi]
// 表示在选修课程 ai 前 必须 先选修 bi
// 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1]
// 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序
// 你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组
// 测试链接 : https://leetcode.cn/problems/course-schedule-ii/
inline std::vector<int> findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites)
{
    std::vector<std::vector<int>> graph(numCourses);
    std::vector<int>              indegree(numCourses);
    for (auto& edge : prerequisites) {
        graph[edge[1]].push_back(edge[0]);
        indegree[edge[0]]++;
    }

    std::vector<int> queue(numCourses);
    int              r = 0, l = 0;
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            queue[r++] = i;
        }
    }

    int cnt = 0;
    while (r > l) {
        int cur = queue[l++];
        cnt++;
        for (auto i : graph[cur]) {
            if (--indegree[i] == 0) queue[r++] = i;
        }
    }

    return cnt == numCourses ? queue : std::vector<int>{};
}

// 字典序最小的拓扑排序
// 要求返回所有正确的拓扑排序中 字典序最小 的结果
// 建图请使用链式前向星方式，因为比赛平台用其他建图方式会卡空间
// 测试链接 : https://www.luogu.com.cn/problem/U107394
class TopoSortStaticLuogu {
    std::vector<int> head;
    std::vector<int> next;
    std::vector<int> to;
    int              cnt;

    std::vector<int>                                              indegree;
    std::priority_queue<int, std::vector<int>, std::greater<int>> queue;
    std::vector<int>                                              ans;

    inline void build(int n, std::vector<std::vector<int>>& prerequisites)
    {
        head = std::vector<int>(n + 1);
        next = std::vector<int>(n + 1);
        to   = std::vector<int>(n + 1);
        cnt  = 1;

        indegree = std::vector<int>(n);
        ans      = std::vector<int>(n);

        for (auto& edge : prerequisites) {
            // e[0]=to,e[1]=from
            next[cnt]     = head[edge[1]];
            to[cnt]       = edge[0];
            head[edge[1]] = cnt++;
            indegree[edge[0]]++;
        }
    }

    inline void topoSort(int len)
    {
        for (int i = 0; i < len; i++) {
            if (indegree[i] == 0) queue.push(i);
        }

        int fill = 0;
        while (!queue.empty()) {
            int cur = queue.top();
            queue.pop();
            ans[fill++] = cur;
            for (int ei = head[cur]; ei != 0; ei = next[ei]) {
                if (--indegree[to[ei]] == 0) queue.push(to[ei]);
            }
        }
    }

public:
    inline void findOrder(int numCourses, std::vector<std::vector<int>>& prerequisites)
    {
        build(numCourses, prerequisites);
        topoSort(numCourses);
        for (auto i : ans) {
            std::printf("%d, ", i);
        }
    }
};

// 火星词典
// 现有一种使用英语字母的火星语言
// 这门语言的字母顺序对你来说是未知的。
// 给你一个来自这种外星语言字典的字符串列表 words
// words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
// 如果这种说法是错误的，并且给出的 words 不能对应任何字母的顺序，则返回 ""
// 否则，返回一个按新语言规则的 字典递增顺序 排序的独特字符串
// 如果有多个解决方案，则返回其中任意一个
// words中的单词一定都是小写英文字母组成的
// 测试链接 : https://leetcode.cn/problems/alien-dictionary/
// 测试链接(不需要会员) : https://leetcode.cn/problems/Jf1JuT/
inline std::string alienOrder(std::vector<std::string>& words)
{
    std::vector<int> indegree(26, -1);
    for (auto& word : words) {
        for (auto c : word) {
            indegree[c - 'a'] = 0;
        }
    }

    std::vector<std::vector<int>> graph(26, std::vector<int>());
    for (int i = 0, j, len; i < words.size() - 1; i++) {
        std::string&  cur  = words[i];
        decltype(cur) next = words[i + 1];
        j                  = 0;
        len                = std::min(cur.size(), next.size());
        for (; j < len; j++) {
            if (cur[j] != next[j]) {
                graph[cur[j] - 'a'].push_back(next[j] - 'a');
                indegree[next[j] - 'a']++;
                break;
            }
        }

        if (j < cur.size() && j == next.size()) return "";
    }

    std::vector<int> queue(26);
    int              l = 0, r = 0;
    int              kinds = 0;
    for (int i = 0; i < indegree.size(); i++) {
        if (indegree[i] != -1) kinds++;
        if (indegree[i] == 0) queue[r++] = i;
    }

    std::string ans;
    while (l < r) {
        int cur = queue[l++];
        ans += (char)('a' + cur);
        for (int next : graph[cur]) {
            if (--indegree[next] == 0) queue[r++] = next;
        }
    }

    return kinds == ans.size() ? ans : "";
}

// 戳印序列
// 你想最终得到"abcbc"，认为初始序列为"?????"。印章是"abc"
// 那么可以先用印章盖出"??abc"的状态，
// 然后用印章最左字符和序列的0位置对齐，就盖出了"abcbc"
// 这个过程中，"??abc"中的a字符，被印章中的c字符覆盖了
// 每次盖章的时候，印章必须完全盖在序列内
// 给定一个字符串target是最终的目标，长度为n，认为初始序列为n个'?'
// 给定一个印章字符串stamp，目标是最终盖出target
// 但是印章的使用次数必须在10*n次以内
// 返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成
// 上面的例子返回[2,0]，表示印章最左字符依次和序列2位置、序列0位置对齐盖下去，就得到了target
// 如果不能在10*n次内印出序列，就返回一个空数组
// 测试链接 : https://leetcode.cn/problems/stamping-the-sequence/
inline std::vector<int> movesToStamp(std::string stamp, std::string target)
{
    int                           m = stamp.size();
    int                           n = target.size();
    std::vector<int>              indegree(n - m + 1, m);
    std::vector<std::vector<int>> graph(n, std::vector<int>());
    std::vector<int>              queue(n - m + 1);
    int                           l = 0, r = 0;
    for (int i = 0; i < n - m + 1; i++) {
        for (int j = 0; j < m; j++) {
            if (target[i + j] == stamp[j]) {
                if (--indegree[i] == 0) queue[r++] = i;
            }
            else {
                graph[i + j].push_back(i);
            }
        }
    }

    // 同一个位置取消错误不要重复统计
    bool* visited = new bool[n];
    std::fill(visited, visited + n, false);
    std::vector<int> path(n - m + 1);
    int              size = 0;
    while (l < r) {
        int cur      = queue[l++];
        path[size++] = cur;
        for (int i = 0; i < m; i++) {
            if (!visited[cur + i]) {
                visited[cur + i] = true;
                for (int next : graph[cur + i]) {
                    if (--indegree[next] == 0) queue[r++] = next;
                }
            }
        }
    }

    delete[] visited;
    if (size != n - m + 1) return {};
    std::reverse(path.begin(), path.end());
    return path;
}
}   // namespace lxj

#endif